The present invention relates to pipelined circuits, and more particularly to pipelined methods and apparatus for weight selection and content addressable memory searches.
Content addressable memories (CAMs) can be used in network routers to perform address translation, filtering, and quality of service (QoS) determination. See PCT Publication WO 98/41922, xe2x80x9cAccelerated Hierarchical Address Filtering and Translationxe2x80x9d, Music Semiconductors, Inc., Sep. 24, 1998. See also A. J. McAuley and P. Francis, xe2x80x9cFast Routing Table Lookup Using CAMsxe2x80x9d, Proceedings of the Conference on Computer Communications, IEEE INFOCOM ""93, pages 1382-1391. Address translation involves examining a packet destination address or connection identifier to determine the router port or ports on which the packet should be transmitted. Filtering involves examining source or destination addresses, or both, and possibly other information, to determine if the packet should be discarded. Determining the quality of service may involve examination of the source and/or destination addresses, and possibly other information, to determine delay parameters, loss priority, or other service parameters for the packet.
Today""s primary application is address translation in network routers. QoS determination, however, is becoming increasingly important in each network element (e.g. each router), and has to be enforced end-to-end across the network. This is driven by the following paradigm shifts in network infrastructure requirements:
1. With the convergence of voice, video, and data onto a common network infrastructure, rigorous QoS guarantees have to be upheld for real-time applications.
2. Through e-commerce and mission-critical applications, high priority delivery has to be guaranteed.
When a packet arrives at a router, the source or destination address or other information in the packet is used to form a key for searching the CAM. If the key matches a CAM entry, the data corresponding to the entry provides the needed information such as the output port on which the packet should be transmitted, or a flag indicating whether or not the packet should be discarded, or a quality of service parameter.
A key can match several entries in the CAM. An entry may have xe2x80x9cdon""t carexe2x80x9d bits. For example, an entry may have the form xe2x80x9c1101 1001 XX...Xxe2x80x9d, where X means xe2x80x9cdon""t carexe2x80x9d. Another CAM entry may have the form xe2x80x9c1101 XXXX XX...Xxe2x80x9d. If the first eight bits of the key are xe2x80x9c1101 1001xe2x80x9d, the key will match both entries. Therefore, the best matching entry (the highest priority entry) has to be determined.
In some circuits, the entries"" priorities are defined by the order of the entries in the CAM. The entries are ordered in the order of descending priorities. The first matching entry is the best match. A disadvantage of this scheme is that the entries have to be rearranged when an entry is added or deleted. Adding and deleting entries in routers can be a frequent occurrence as routers and communication links are put in and out of service.
Another approach is to allocate a separate block of memory for entries of each priority. Adding and deleting of entries becomes easier. However, memory use is inefficient. If a memory block allocated for some priority gets full, additional entries destined for the block cannot be placed in other blocks even if the other blocks have memory available.
Another solution is to store the priority of each entry explicitly. Only the entries of the highest priority are searched. If no matching entry is found, the entries of the next highest priority are searched, and so on. Disadvantageously, the CAM may have to be searched many times before the best match is determined.
The aforementioned PCT Publication WO 98/41922 describes a technique requiring only two CAM searches. In that technique, each priority has only one bit set (i.e., only one bit has a value 1). When the CAM is searched for the first time, the search is performed among all the entries. The priorities of the matching entries are ORed. The most significant bit of the result of the OR operation defines the highest priority for which a match has occurred. When the CAM is searched for the second time, the search covers only the entries of the highest priority determined from the OR operation.
Improvements on these techniques are desirable.
According to the present invention, the priority of each CAM entry is stored explicitly, and is indicated by a number that we will call a xe2x80x9cweightxe2x80x9d of the CAM entry. Selection of the highest priority entry is pipelined. For example, the selection process includes xe2x80x9cNxe2x80x9d pipeline stages, where Nxe2x89xa72. We will call these pipeline stages xe2x80x9cstage 0xe2x80x9d, xe2x80x9cstage 1xe2x80x9d, and so on.
When the CAM has been searched, the pipeline stage 0 selects one or more of the weights based on one or more bits of each weight participating in the selection. Each pipeline stage i (ixe2x89xa71) selects one or more of the weights from the weights selected at the pipeline stage i-1.
In some embodiments, pipeline stage 0 selects weights based on the most significant bit of each weight. Pipeline stage 1 selects weights based on the next most significant bit (e.g., bit xe2x80x9c1xe2x80x9d if the most significant bit is denoted bit xe2x80x9c0xe2x80x9d). If the pipeline stage 2 is present, it selects weights based on the next most significant bit (bit 2), and so on.
Since a pipeline stage performed for one key can overlap with other pipeline stages performed for other keys, high throughput is achievable.
In some embodiments, the CAM can be searched only once, so the CAM searches for different keys can be easily pipelined.
In some network applications the CAM of the present invention provides fixed single clock cycle search throughput, independent of the network loading or traffic characteristics. Some embodiments also provide fixed time single-entry insertion table updates (adding a single entry with its associated weight takes a fixed amount of time) because the entries do not have to be ordered in the CAM. High throughput (e.g. single clock cycle throughput) allows the QoS determination for each incoming packet to be performed before the packet is queued in the network element. Fixed time QoS packet processing before the first queuing point in the network element facilitates guaranteeing QoS levels to the end user.
The invention is not limited to the number of weight bits examined at each pipeline stage, the number of CAM searches per key, or even to CAM searches. For example, the pipelined weight selection techniques of the invention are used to arbitrate access to a shared resource. Each entity sharing the resource has a priority defined based on a corresponding weight. Pipelined weight selection is performed to select the highest priority entities requesting access to the resource.
Other features and advantages of the invention are described below. The invention is defined by the appended claims.